import pygame
import sys
import random
import time
from pygame.locals import *

# 初始化Pygame库
pygame.init()

# 初始化一个游戏界面窗口
DISPLAY = pygame.display.set_mode((300, 300))

# 设置游戏窗口的标题
pygame.display.set_caption('贪吃蛇')

# 定义一个变量来控制游戏速度
FPSCLOCK = pygame.time.Clock()

# 初始化游戏界面内使用的字体
BASICFONT = pygame.font.SysFont("SIMYOU.TTF", 80)
font = pygame.font.SysFont('simsunnsimsun', 80)

# 设置颜色
BLACK = pygame.Color(0, 0, 0)
WHITE = pygame.Color(255, 255, 255)
RED = pygame.Color(255, 0, 0)
GREY = pygame.Color(150, 150, 150)
GREEN = pygame.Color(0, 255, 255)
YELLOW = pygame.Color(255, 255, 0)
FORESTGREEN = pygame.Color(34, 139, 34)
Purple3 = pygame.Color(125, 38, 205)

# 贪吃蛇头的初始位置
snake_Head = [100, 100]

# 初始化贪吃蛇的身体 (注：这里以20*20为一个标准小格子)
snake_Body = [[80, 100], [60, 100], [40, 100]]

# 指定蛇初始前进的方向 -- 向右
direction = "RIGHT"


def randomfood(snake_Body):
    """随机生成食物"""

    # 随机生成食物的位置
    x = random.randrange(1, 15)
    y = random.randrange(1, 15)
    Position = [int(x * 20), int(y * 20)]

    # 如果食物在贪吃蛇的身体里，则重新随机
    while Position in snake_Body:
        x = random.randrange(1, 15)
        y = random.randrange(1, 15)
        Position = [int(x * 20), int(y * 20)]
    return Position


# 随机出现第一个食物
food_Position = randomfood(snake_Body)

# 标记食物
food_flag = 1


def GameOver():
    """游戏结束"""

    # 设置GameOver的显示颜色与文字
    if (len(snake_Body) - 3) <= 10:
        GameOver_Surf = font.render('太菜了', True, GREY)
    elif 10 <= (len(snake_Body) - 3) <= 20:
        GameOver_Surf = font.render('一般般', True, GREY)
    else:
        GameOver_Surf = font.render('很棒！', True, GREY)

    # 设置GameOver的位置
    GameOver_Rect = GameOver_Surf.get_rect()
    GameOver_Rect.midtop = (320, 200)

    # 绑定以上设置到句柄
    DISPLAY.blit(GameOver_Surf, GameOver_Rect)

    # 刷新画面
    pygame.display.flip()

    # 等待3秒
    time.sleep(3)
    # 退出游戏
    pygame.quit()
    # 退出程序
    sys.exit()


def walkable(location0, snake_body0):
    """返回下一步可以到达的位置"""
    l = []

    # 向右
    if location0[0] + 20 < 300 and [location0[0] + 20, location0[1]] not in snake_body0:
        l.append([location0[0] + 20, location0[1]])

    # 向左
    if location0[0] - 20 >= 0 and [location0[0] - 20, location0[1]] not in snake_body0:
        l.append([location0[0] - 20, location0[1]])

    # 向下
    if location0[1] + 20 < 300 and [location0[0], location0[1] + 20] not in snake_body0:
        l.append([location0[0], location0[1] + 20])

    # 向上
    if location0[1] - 20 >= 0 and [location0[0], location0[1] - 20] not in snake_body0:
        l.append([location0[0], location0[1] - 20])

    return l


def changexy(position0):
    """改变位置"""
    position = position0.copy()
    return position[1] * 15 + position[0]


def BFS(food_position0, snake_body0):
    # 获取食物的位置
    food_position = food_position0.copy()
    # 获取贪吃蛇的身体信息
    snake_body = snake_body0.copy()

    # 是否可以吃到食物
    flag = 0

    # 存储路径
    path = []

    # 搜索栈，广度优先搜索
    search_stack = []

    # {下一个位置：当前位置}
    visited_dict = {}
    search_stack.append([snake_body[0][0], snake_body[0][1]])
    visited_dict[changexy([snake_body[0][0], snake_body[0][1]])] = -1

    # 进行广度优先遍历
    while len(search_stack) > 0:
        # 获取贪吃蛇头当前位置
        currentlocation = search_stack.pop(0)

        # 如果当前没有吃到食物
        if currentlocation != food_position:

            # 记录下一步可以走到的位置，不考虑蛇身更新情况
            l1 = walkable(currentlocation, snake_body)

            # 遍历下一步的所有可能
            for i in l1:
                if visited_dict.get(changexy(i)) == None:
                    search_stack.append(i)
                    visited_dict[changexy(i)] = currentlocation

        # 如果吃到该食物
        else:
            flag = 1
            break

    # 添加食物位置进路径
    path.append(currentlocation)

    # 不断将前一个位置添加进路径
    while visited_dict[changexy(currentlocation)] != -1:
        currentlocation = visited_dict[changexy(currentlocation)]
        path.append(currentlocation)

    # 反转 --> 贪吃蛇的头到食物的路径
    path.reverse()

    return path, flag


def tailBFS(tail_position0, snake_body0):
    # 蛇尾、蛇身
    tail_position = tail_position0.copy()
    snake_body = snake_body0.copy()

    # 记录是否能到蛇尾
    flag = 0

    # 记录到蛇尾的路径
    path = []

    # 搜索栈
    search_stack = []

    # {下一个位置：当前位置}
    visited_dict = {}

    # 初始化
    search_stack.append([snake_body[0][0], snake_body[0][1]])
    visited_dict[changexy([snake_body[0][0], snake_body[0][1]])] = -1

    # 开始广度优先遍历
    while len(search_stack) > 0:
        # 获取当前位置
        currentlocation = search_stack.pop(0)

        if currentlocation != tail_position:
            # l1存储下一步可走的位置，蛇尾是可到达的
            tail = snake_body.pop()
            l1 = walkable(currentlocation, snake_body)
            snake_body.append(tail)

            # 遍历各个可走位置
            for i1 in l1:
                if visited_dict.get(changexy(i1)) == None:
                    # 更新搜索栈
                    search_stack.append(i1)
                    # 记录位置点间的关系
                    visited_dict[changexy(i1)] = currentlocation
        else:
            flag = 1
            break

    return flag


def exploretheway(food_position0, snake_body0):
    # 获取蛇身与食物位置
    snake_body = snake_body0.copy()
    food_position = food_position0.copy()

    while True:
        # 获取觅食路径
        path, flag1 = BFS(food_position, snake_body)

        # 更新蛇头
        snake_body.insert(0, path[1])

        # 如果吃到食物
        if snake_body[0][0] == food_position[0] and snake_body[0][1] == food_position[1]:

            # 当前位置是否能找到尾巴
            flag2 = tailBFS(snake_body[-1], snake_body)

            break
        # 未吃到食物，则更新蛇尾
        else:
            snake_body.pop()
    return flag2


def longest_tail_path(snake_body0):
    """返回最长的蛇尾路径"""

    # 获取蛇身
    snake_body = snake_body0.copy()

    # 获取下一步可以走的路，蛇尾是可以走的
    tail = snake_body.pop()
    l0 = walkable(snake_body[0], snake_body)
    snake_body.append(tail)

    longest = -1

    # 遍历下一步可能的情况，如A\B\C
    # 再分别利用广度优先搜索，在A\B\C的情况下，找出到蛇尾的最短路径
    # 如果A情况下最短路径是最长的，则下一步往A处走
    for i0 in l0:
        flag = 0
        path = []
        search_stack = []
        visited_dict = {}

        # 搜索栈 -- 广度优先遍历
        search_stack.append(i0)

        # {下一个位置：当前位置}
        visited_dict[changexy(i0)] = -1

        # 广度搜索
        while len(search_stack) > 0:

            # 更新当前位置
            currentlocation = search_stack.pop(0)

            # 如果不在蛇尾
            if currentlocation != snake_body[-1]:

                # l1记录所有下一位置的可能
                tail = snake_body.pop()
                l1 = walkable(currentlocation, snake_body)
                snake_body.append(tail)

                # 遍历下一位置的可能
                for j in l1:
                    if visited_dict.get(changexy(j)) == None:

                        # 更新搜索栈
                        search_stack.append(j)

                        # 更新各位置的先后关系
                        visited_dict[changexy(j)] = currentlocation

            else:
                # 找到了一条到达蛇尾的路径
                flag = 1
                break

        # 记录路径信息
        path.append(currentlocation)
        while visited_dict[changexy(currentlocation)] != -1:
            currentlocation = visited_dict[changexy(currentlocation)]
            path.append(currentlocation)
        path.reverse()

        # 如果有更长的路径，则更新最长路径
        if flag == 1:
            if len(path) > longest:
                longest = len(path)
                longest_path = path

    return longest_path


# 漫步函数，随机选择蛇头周围四个方向中可走的方向走一步
def wander(snake_body0):
    # 获取下一步可以走的路径
    l = walkable(snake_body0[0], snake_body0)

    # 随机走一步
    if len(l) > 1:
        x = random.randrange(0, len(l))
    elif len(l) == 1:
        x = 0
    else:
        return l
    return l[x]

def drawSnake(snake_body0):

    # 画蛇头（x, y, width, length）
    pygame.draw.rect(DISPLAY, Purple3, Rect(
        snake_body0[0][0], snake_body0[0][1], 20, 20))

    # 画蛇身
    for j in range(1, len(snake_body0)-1):
        pygame.draw.rect(DISPLAY, FORESTGREEN, Rect(
            snake_body0[j][0], snake_body0[j][1], 20, 20))

    # 画蛇尾
    pygame.draw.rect(DISPLAY, GREEN, Rect(
        snake_body0[-1][0], snake_body0[-1][1], 20, 20))

def drawFood(food_position0):
    # 画食物
    pygame.draw.rect(DISPLAY, RED, Rect(
        food_position0[0], food_position0[1], 20, 20))

def drawScore(score):
    # 设置分数的显示颜色
    score_Surf = BASICFONT.render('%s' % (score), True, GREY)
    # 设置分数的位置
    score_Rect = score_Surf.get_rect()
    score_Rect.midtop = (50, 20)
    # 绑定以上设置到句柄
    DISPLAY.blit(score_Surf, score_Rect)

while True:
    # 蛇身不动，蛇头动，是否可以吃到食物，返回最短路径
    food_path, food_flag = BFS(food_Position, snake_Body)

    # 蛇身不动，蛇头动，尾巴是否可到达
    tail_flag = tailBFS(snake_Body[-1], snake_Body)

    # 当前布局能找到吃food_path
    if food_flag == 1:
        # 虚拟蛇探路，吃到食物后如果能找到tail_path则返回1
        virtual_tail_flag = exploretheway(food_Position, snake_Body)

        # 虚拟蛇吃完食物后找得到tail_path
        if virtual_tail_flag == 1:
            print("安全路径吃食物")

            # 真实的蛇沿最短路径向食物走一步
            snake_Body.insert(0, food_path[1])

            # 吃到食物，则重新随机食物位置
            if snake_Body[0][0] == food_Position[0] and snake_Body[0][1] == food_Position[1]:
                food_Position = randomfood(snake_Body)

            # 未吃到食物，则更新蛇尾
            else:
                snake_Body.pop()

        # 虚拟蛇吃完食物后找不到tail_path
        else:
            print("直接吃不安全，找蛇尾")

            # 真实的蛇沿最长路径向蛇尾走一步
            longest_path = longest_tail_path(snake_Body)

            # 更新蛇身
            snake_Body.insert(0, longest_path[0])
            if snake_Body[0][0] == food_Position[0] and snake_Body[0][1] == food_Position[1]:
                food_Position = randomfood(snake_Body)
            else:
                snake_Body.pop()

    # 当前布局能找到tail_path（找不到food_path）
    elif tail_flag == 1:
        print("找到蛇尾")
        # 真实的蛇沿最长路径向蛇尾走一步
        longest_path = longest_tail_path(snake_Body)

        # 更新蛇身
        snake_Body.insert(0, longest_path[0])
        snake_Body.pop()

    # 找不到food_path也找不到tail_path时。随机走一步
    elif food_flag != 1 and tail_flag != 1:
        print("找不到食物也找不到蛇尾")

        # 无路可走
        if len(wander(snake_Body)) == 0:
            print("走投无路")
            GameOver()
            break

        # 有路可走
        else:
            snake_Body.insert(0, wander(snake_Body))
            snake_Body.pop()

    # 画布为黑色
    DISPLAY.fill(BLACK)

    # 画出贪吃蛇
    drawSnake(snake_Body)

    # 画出食物的位置
    drawFood(food_Position)

    # 打印出玩家的分数
    drawScore(len(snake_Body) - 3)

    # 刷新Pygame的显示层，贪吃蛇与食物的每一次移动，都会进行刷新显示层的操作来显示。
    pygame.display.flip()

    # 控制游戏速度
    FPSCLOCK.tick(20)

    # 蛇碰到边缘，游戏结束
    if snake_Body[0][0] < 0 or snake_Body[0][0] > 300:
        GameOver()
    if snake_Body[0][1] < 0 or snake_Body[0][1] > 300:
        GameOver()

    # 贪吃蛇头触碰到自己，游戏结束
    for i in snake_Body[1:]:
        if snake_Body[0][0] == i[0] and snake_Body[0][1] == i[1]:
            GameOver()